package com.code.test.second.link;

/**
 * 206
 * 题意：反转一个单链表。
 * <p>
 * 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
 */
public class SCode24 {
    public static void main(String[] args) {
        SNode head = new SNode(1);
        SNode second = new SNode(2);
        SNode third = new SNode(3);
        SNode n4 = new SNode(4);
        SNode n5 = new SNode(5);
//        SNode n6 = new SNode(6);
//        SNode n7 = new SNode(7);

        head.setNext(second);
        second.setNext(third);
        third.setNext(n4);
        n4.setNext(n5);
//        n5.setNext(n6);
//        n6.setNext(n7);

        SNode swaped = swap2(head);

        int a = 2;
    }

    //虚拟头结点，交换指针
    public static SNode reverse(SNode head) {
        //虚拟头结点
        SNode dummyHead = new SNode(-1);
        dummyHead.next = head;
        SNode firstNode;
        SNode secondNode;

        SNode cur = dummyHead;
        //这个保存的是第三个节点，即dummy->first-second->tmp
        SNode tmp;
        //第一个是dummy，要交换，必须得后2个都存在
        while (cur.next != null && cur.next.next != null) {
            tmp = cur.next.next.next;
            firstNode = cur.next;
            secondNode = cur.next.next;

            cur.next = secondNode;
            secondNode.next = firstNode;
            firstNode.next = tmp;

            //cur往前移动，继续换下一个
            cur = firstNode;
        }
        return dummyHead.next;

    }

    /**
     * 递归版本
     * <p>
     * 每个swap返回的都是当前节点的下一个
     */
    public static SNode swap(SNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }

        SNode next = cur.next;
        /**
         * swap的返回值是当前节点的下一个的下一个,cur.next.next
         * 把当前节点.next = cur
         * 把cur.next = swap返回的节点
         * 这样就完成了第一组节点的交换
         * ------------
         *
         */
        SNode newNode = swap(next.next);
        next.next = cur;
        cur.next = newNode;
        return next;
    }

    public static SNode swap2(SNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        //找到下一个节点
        SNode next = cur.next;
        //再找到下下一个节点
        SNode newNode = swap2(next.next);
        /**
         * 现在总计有3个节点，cur->cur.next->cur.next.next
         * cur.next = cur.next.next.next
         * 举个例子: 1->2->3->4
         * 转换后:2->1->4->3
         * 1应该直接连到4，所以是 cur.next.next.next
         * 以此类推，每一个都这么换
         */
        next.next = cur;
        cur.next = newNode;
        return next;
    }
}
